package uk.org.landeg.euler.problems.lib;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class NumbersLib {
	public static long numlens[] = new long [] {
		1,
		10,
		100,
		1000,
		10000,
		100000,
		1000000,
		10000000,
		100000000,
		1000000000,
		10000000000L,
		100000000000L,
		1000000000000L,
		10000000000000L,
		100000000000000L,
		1000000000000000L,
		10000000000000000L,
		100000000000000000L,
		1000000000000000000L};
	
	public static void main(String[] args) {
//		testSumRange();
//		testFacorise();
//		testisPalindrome();
//		ArrayList<Long> primes = PrimeLib.seqPrimes(30000L);
		int n = 12345;
		int rot = n;
		do {
			rot = rotateDigits(rot);
			System.out.println(rot);
		} while (n != rot);
		
		n = 123456;
		System.out.println(containsDigits(n, new int[]{7,6,9}));
//		System.out.println(rotateDigits(12345));
	}

	public static long sumRange(int min, int max) {
		return (min + max) * (max - min + 1) / 2;
	}
	
	public static Set<Long> quickPrimeFactors (long n, ArrayList<Long> primes) {
		if (primes == null) {
			primes = PrimeLib.seqPrimes((long)Math.sqrt(n));
		}
		Set<Long> factors = new TreeSet<Long>();
		for (long trial : primes) {
			if (trial * trial > n) {
				break;
			}
			if (n % trial == 0) {
				factors.add(n);
			}
		}
		return factors;
	}
	
	/**
	 * get all factors of n where it's prime factors are already known
	 * @param n
	 * @param proper
	 * @param primeFactors
	 * @return
	 */
	public static Set<Long> getFactors (long n, boolean proper, Set<Long> primeFactors) {
		Set<Long> factors = new TreeSet<Long>();
		factors.addAll(primeFactors);
		int scale;
		long trial;
		long max = (long)Math.sqrt(n)/2;
		factors.add(1L);
		factors.add(n);
		for (long pf : primeFactors) {
			scale = 2;
			while ((trial = pf * scale) < max) {
				if (n % trial == 0) {
					factors.add(trial);
					factors.add(n/trial);
				}
				scale++;
			}
		}
		return factors;
	}
	
	public static int[] getDigits (int n) {
		int[] digits = new int[numericLength(n)];
		int idx = digits.length - 1;
		do {
			digits[idx--] = (n % 10);
			n /= 10;
		} while (n > 0);
		return digits;
	}
	
	public static Set<Long> getDivisors (long n) {
		Set<Long> factors = getFactors(n, true);
		factors.add(1L);
		return factors;
	}
	
	public static int replaceDigits (int n, int search, int replace) {
		int digits[] = getDigits(n);
		for (int idx = 0 ; idx < digits.length ; idx++) {
			if (digits[idx] == search) {
				digits[idx] = replace;
			}
		}
		return intFromDigits(digits);
	}

	public static int intFromDigits (int[] digits) {
		int ret = 0;
		int mult = 1;
		for (int idx = digits.length - 1 ; idx >= 0 ; idx--) {
			ret += digits[idx] * mult;
			mult *= 10;
		}
		return ret;
	}
	
	public static Set<Long> getFactors (long n, boolean proper) {
		Set<Long> factors = new TreeSet<Long>();
		long maxCheck = (long)(Math.sqrt(n) + 1);
		long start = (proper) ? 2 : 1;
		for (long idx = start ; idx < maxCheck ; idx++) {
			if (n % idx == 0) {
				factors.add(idx);
				factors.add(n/idx);
			}
		}
		return factors;
	}

	public static Map<Long,Integer> factorise(long n) {
		Map<Long,Integer> ret = new HashMap<Long,Integer>();
		long trial = 2;
		long maxTrial = (long)(Math.sqrt(n) + 2), other;
		Integer current;
		do {
			if (n % trial == 0) {
				other = n / trial;
				if (other == trial) {
					ret.put(trial, 2);
				} else {
					n /= trial;
					current = ret.get(trial);
					if (current == null) {
						current = 0;
					}
					ret.put(trial, current + 1);
					current = ret.get(other);
					if (current == null) {
						current = 0;
					}
					ret.put(other, current + 1);
					System.out.println(trial);
				}
			}
		} while (++trial < maxTrial);
		return ret;
	}
	
	public static Map<Long,Integer> primeFactors (long n) {
		Map<Long,Integer> ret = new HashMap<Long, Integer>();
		List<Long> primes = PrimeLib.seqPrimes(n);
		if (primes.contains(n)) {
			// n is itself prime
			ret.put(n,1);
		} else {
			Iterator<Long> pit = primes.iterator();
			int power; 
			long thisPrime;
			while (pit.hasNext() && n > 1) {
				power = 0;
				thisPrime = pit.next();
				while (n % thisPrime == 0) {
					n /= thisPrime;
					power++;
				}
				if (power > 0) {
					ret.put(thisPrime, power);
				}
			}
		}
		return ret;
	}
	
	/** for large products - take a series of terms and finds the prime factors. **/
	public static Map<Long,Integer> primeFactorSeries (int values[]) {
		Map<Long,Integer> ret = new HashMap<Long, Integer>();
		Map<Long,Integer> theseFactors;
		for (int i : values) {
			theseFactors = primeFactors(i);
			for (long key : theseFactors.keySet()) {
				if (!ret.containsKey(key)) {
					ret.put(key, 0);
				}
				try {
					ret.put(key, ret.get(key) + theseFactors.get(key));
				} catch (Exception e) {
					System.out.println("key = " + key + "  ret = " + ret);
				}
			}
		}
		return ret;
	}
	
	public static boolean isPalindrome (long n) {
		int digits[] = new int[(int)Math.log10(n) + 1];
		int loc = 0;
		while (n > 0) {
			digits[loc++] = (int)(n % 10);
			n /= 10;
		}
		for (int idx = 0; idx < digits.length / 2 ; idx++) {
			if (digits[idx] != digits[digits.length - 1 - idx]) {
				return false;
			}
		}
		return true;
	}
	
	public static long tetrahedralNumber (long n) {
		return (2 * n * n * n + 3 * n * n + n)/6;
	}
	
	public static long triangle (long n) {
		return (n + n * n)/ 2;
	}
	
	public static int hexagonal (int n) {
		return (n * (2*n -1));
	}
	
	public static int pentagonal (int n) {
		return (n * (3*n -1) / 2);
	}

	public static long hexagonal (long n) {
		return (n * (2*n -1));
	}
	
	public static long pentagonal (long n) {
		return (n * (3*n -1) / 2);
	}

//	private static void testSumRange() {
//		System.out.println("add 1..10 : " + sumRange(1, 10));
//		System.out.println("add 2..10 : " + sumRange(2, 10));
//		System.out.println("add 2..10 : " + sumRange(2, 9));
//		System.out.println("add 2..10 : " + sumRange(2, 8));
//	}
//
//	private static void testFacorise () {
//		System.out.println("Factorising 100 : " + factorise(100));
//	}
//	
//	private static void testisPalindrome () {
//		System.out.println("testisPalindrome");
//		long[] values= {123456,65656565,65656,12345654321L};
//		for (long l : values) {
//			System.out.println("Testing " + l + " \t : " + isPalindrome(l));
//		}
//	}
	
	public static long sumDigits (String s) {
		char[] digits = s.toCharArray();
		long sum = 0;
		for (char c : digits) {
			sum += (int)c - (int)'0';
		}
		return sum;
	}
	
	public static int sumDigits (long n) {
		int sum = 0;
		while (n > 0) {
			sum += n % 10;
			n /= 10;
		}
		return sum;
	}
	
	public static long sum (Collection<Long> c) {
		Long total = 0L;
		for (Long l : c) {
			total += l;
		}
		return total;
	}		
	
	public static int[] getDigits (long n) {
		int[] rtn = new int[(int)(Math.log10(n) + 1)];
		for (int idx = rtn.length - 1 ; idx >= 0 ; idx--) {
			rtn[idx] = (int)n%10;
			n /= 10;
		}
		return rtn;
	}
	
	public static int rotateDigits (int i) {
		int digits = (int)(Math.log10(i) + 1);
		int mult = i % 10;
		return (i / 10) + mult * (int)Math.pow(10, digits-1);
	}
	
	public static int[] digitCount (int i) {
		int digits[] = getDigits(i);
		int sum[] = new int[10];
		for (int d : digits) {
			sum[d]++;
		}
		return sum;
	}
	
	public static boolean containsDigits(int n, int[] digits) {
		int d;
		do {
			d = n % 10;
			for (int test : digits) {
				if (test == d) {
					return true;
				}
			}
			n /= 10;
		} while (n > 1);
		return false;
	}
	
	public static long factorial (int n) {
		long ret =1;
		if (n > 0) {
			do {
				ret *= n;
			} while (--n >0);
		}
		return ret;
	}
	
	public static BigInteger bigFactorial (int n) {
		BigInteger ret = BigInteger.valueOf(1L);
		if (n > 0) {
			do {
				ret.multiply(BigInteger.valueOf(n));
			} while (--n >0);
		}
		return ret;
	}
	
	public static long PI (int n1, int n2) {
		long result = 1;
		for (int n = n1 ; n <= n2 ; n++) {
			result *= n;
		}
		return result;
	}
	
	public static void normalizeDigitArray (int[] digits) {
		for (int n = digits.length - 1 ; n > 0 ; n--) {
			while (digits[n] >= 10) {
				digits [n-1] += digits[n]/10;
				digits[n] -= digits[n]/10 * 10;
			}
		}
		digits[0] -= digits[0]/10 * 10;
	}	
	
//	public static boolean isPandigital
	public static boolean isPandigital (int n) {
		int count[] = digitCount(n);
		for (int i = 1; i  < count.length ; i++) {
			if (count[i] != 1) {
				return false;
			}
		}
		return true;
	}
	
	public static int numericLength (long n) {
		for (int i = 0; i < numlens.length ; i++) {
			if (n < numlens[i]) {
				return i;
			}
		}
		return -1;
	}
	
	public static boolean isPalindrome (BigInteger n) {
		char chars [] = n.toString().toCharArray();
		for (int idx = 0 ; idx < (int)(chars.length/2) ; idx++) {
			if (chars[idx] != chars[chars.length - idx -1 ]) {
				return false;
			}
		}
		return true;
	}
	
	public static long reverseDigits (long n) {
		long ret = 0;
		int len = NumbersLib.numericLength(n);
		for (int idx = 1 ; idx <= len ; idx++) {
			if (n < 10) {
				ret += n;
			} else {
				ret += (n % 10) * NumbersLib.numlens [len-idx]; 
				n/=10;
			}
		}
		return ret;
	}

	public static long ncr (int n, int r) {
		long result =1;
		int m = n;
		do {
			result *= m--;
		} while (m > r);
		m = n - r;
		do {
			result /= m--;
		} while (m > 1);
		return result;
	}
	
	public static long ncrL (int n, int r) {
		BigInteger val = BigInteger.valueOf(1);
		for (int x = 2 ; x <= n ; x++) {
			val = val.multiply(BigInteger.valueOf(x));
		}
		for (int x = 2 ; x <= r ; x++) {
			val = val.divide(BigInteger.valueOf(x));
		}
		for (int x = n-r ; x > 1 ; x--) {
			val = val.divide(BigInteger.valueOf(x));
		}
		return val.longValue();
	}
	
	public static double logFactorial (int n) {
		double sum = 0.0;
		while (n > 0) {
			sum += Math.log10(n--);
		}
		return sum;
	}
	
	/**
	 * concat n2 to n1
	 * @param n1
	 * @param n2
	 * @return
	 */
	public static long concat (long n1, long n2) {
		n1 *= numlens[numericLength(n2)];
		return n1 + n2;
	}
}
